/**
 * @author tmh
 * @date 2024/9/13 21:48
 * @description
 * 这里要注意一个细节，就是 for 循环中，i < nums.length - 1，少了末尾。因为开始的时候边界是第 0 个位置，steps 已经加 1 了。
 * 如果最后一步刚好跳到了末尾，此时 steps 其实不用加 1 了。如果是 i < nums.length，i 遍历到最后的时候，会进入 if 语句中，steps 会多加 1。
 *
 * 作者：windliang
 * 链接：https://leetcode.cn/problems/jump-game-ii/solutions/9347/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by-10/
 * 来源：力扣（LeetCode）
 * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
 */
public class T45跳跃游戏II {
    public int jump(int[] nums) {
        //记录跳远的最远位置，一开始还没有跳，最远位置就在起始位置，起始位置的下标为0，所以初始值是0
        int maxPosition = 0;
        //记录步数step
        int step = 0;
        //记录跳跃的结束位置
        int end = 0;
        for (int i = 0; i < nums.length; i++) {
            //更新跳跃的最远位置
            maxPosition = Math.max(maxPosition, i + nums[i]);
            //如果跳到了上一次的结束位置，那么就更新结束位置end
            if (i == end) {
                end = maxPosition;
                step++;
            }
        }
        return step;
    }
}
